package algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 一种特殊的单链表节点的描述如下：
 * class Node{
 *     int value;
 *     Node next;
 *     Node rand;
 *     Node(int val){
 *         value = val;
 *     }
 * }
 * rand指针是单链表节点结构中新增的指针， rand可能指向链表中的任意一个节点，
 * 也可以指向null。 给定一个由Node节点类型组成的无环单链表的头节点head，请
 * 实现一个函数完成这个链表的复制， 并返回复制的新链表的头节点。
 * 要求： 时间复杂度为O(N), 额外空间复杂度为O(1)
 *
 * 实现方案：
 *  1.  采取map键值对方式，存储老新节点
 *  2.  在原有链表上，copy一份节点
 *
 */
public class 复制含有随机指针节点的链表 {

    public static class Node{
        int value;
        Node next;
        Node rand;
        Node(int val){
            value = val;
        }
    }

    /**
     * map形式复制
     * @param head
     * @return
     */
    public static Node copyListWithRand1(Node head){

        Map<Node, Node> map = new HashMap<Node, Node>();

        //遍历put到map
        Node cur = head;
        while(cur != null){
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        cur = head;
        while(cur != null){
            map.get(cur).rand = cur.rand;
            map.get(cur).next = cur.next;
            cur = cur.next;
        }

        return map.get(head);
    }

    /**
     * 采取
     * @param head
     * @return
     */
    public static Node copyListWithRand2(Node head){

        //遍历，在节点之后copy一个节点
        Node cur = head;
        Node next = null;
        while(cur != null){
            Node newNode = new Node(cur.value);

            next = cur.next;

            cur.next = newNode;
            newNode.next = next;

            cur = next;
        }


        // copy rand节点

        cur = head;

        while(cur != null){

            next = cur.next.next;
            cur.next.rand = cur.rand ==null? null: cur.rand.next;

            cur = next;

        }

        Node res = head.next;
        cur = head;

        Node curCopy = null;

        //split
        while(cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next: null;
            cur = next;

        }

        return res;
    }


}
